package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-09 19:28
 **/
public class LeetCode2132 {

    public static boolean possibleToStamp(int[][] grid, int h, int w) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] sum = new int[m + 1][n + 1];
        int[][] diff = new int[m + 1][n + 1];
        //遍历计算二维前缀和
        for(int i = 1; i <= m;i++){
            for(int j = 1; j <= n;j++){
                sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + grid[i - 1][j - 1];
            }
        }
        for(int i = 0; i < m;i++){
            for(int j = 0; j < n;j++){
                if(grid[i][j] == 0){
                    int x = i + h, y = j + w ;
                    if(x <= m && y <= n && (sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j] == 0)){
                        diff[i][j]++;
                        diff[i][y]--;
                        diff[x][j]--;
                        diff[x][y]++;
                    }
                }
            }
        }
        int[] cnt = new int[n + 1];
        int[] pre = new int[n + 1];
        for(int i = 0; i < m;i++){
            for(int j = 0; j < n;j++){
                cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff[i][j];
                if(cnt[j + 1] == 0 && grid[i][j] == 0) {
                    return false;
                }
            }
            int[] tmp = cnt;
            cnt = pre;
            pre = tmp;
        }
        return true;
    }

    public static void main(String[] args) {
        possibleToStamp(new int[][]{{1,0,0,0}, {1,0,0,0}, {1,0,0,0},{1,0,0,0},{1,0,0,0,0}}, 4, 3);
    }

}
